// 求完全二叉树的节点个数
// 测试链接 : https://leetcode.cn/problems/count-complete-tree-nodes/
public class Code09_CountCompleteTreeNodes {

    // 不提交这个类
    // TreeNode类用于表示二叉树的节点，其中val表示节点的值，left和right分别表示左子节点和右子节点
    public static class TreeNode {
        public int val;
        public TreeNode left;
        public TreeNode right;
    }

    // 提交如下的方法
    public static int countNodes(TreeNode head) {
        // 如果根节点head为null，说明树为空，节点个数为0，直接返回0
        if (head == null) {
            return 0;
        }
        // 调用f方法计算节点个数，传入根节点head、根节点所在层数为1（假设根节点在第1层）以及整棵树的高度（通过mostLeft(head, 1)获取）
        return f(head, 1, mostLeft(head, 1));
    }

    // cur : 当前来到的节点
    // level : 当前来到的节点在第几层
    // h : 整棵树的高度，不是cur这棵子树的高度
    // 求 : cur这棵子树上有多少节点
    public static int f(TreeNode cur, int level, int h) {
        // 如果当前节点所在层数level等于整棵树的高度h，说明当前节点是叶节点，叶节点个数为1，直接返回1
        if (level == h) {
            return 1;
        }
        // 计算cur右子树的最左高度（即从cur的右子节点开始不停往左能到达的层数）
        if (mostLeft(cur.right, level + 1) == h) {
            // cur右树上的最左节点，扎到了最深层
            // 这意味着cur的右子树是满二叉树，根据满二叉树节点个数公式2^(树高 - 1)，这里右子树高度为h - level
            // 右子树节点个数为(1 << (h - level))，然后递归计算左子树节点个数并相加（再加1表示当前节点cur自身）
            return (1 << (h - level)) + f(cur.right, level + 1, h);
        } else {
            // cur右树上的最左节点，没扎到最深层
            // 这意味着cur的左子树是满二叉树，左子树高度为h - level - 1
            // 左子树节点个数为(1 << (h - level - 1))，然后递归计算右子树节点个数并相加（再加1表示当前节点cur自身）
            return (1 << (h - level - 1)) + f(cur.left, level + 1, h);
        }
    }

    // 当前节点是cur，并且它在level层
    // 返回从cur开始不停往左，能扎到几层
    public static int mostLeft(TreeNode cur, int level) {
        // 只要当前节点cur不为null，就继续往左走
        while (cur!= null) {
            // 层数level加1
            level++;
            // 更新当前节点为其左子节点
            cur = cur.left;
        }
        // 最后返回到达的层数减1，因为最后一次循环多加了1
        return level - 1;
    }
}